package Day2025_03_12;

public class LeetCode91 {
    public int numDecodings(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        if (ch[0] == '0') return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1; dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (ch[i - 1] != '0') dp[i] += dp[i - 1];
            if (ch[i - 2] != '0' && (ch[i - 2] - '0') * 10 + (ch[i - 1] - '0') <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];
    }
    public static void main(String[] args) {
        LeetCode91 leetCode91 = new LeetCode91();
        System.out.println(leetCode91.numDecodings("12"));
    }
}
